量子计算的过去、现在和未来

量子计算与量子信息的研究对象是使用量子力学系统能够完成的信息处理任务。听起来很简单明了，对吗？但像许多简单而深刻的思想一样，人们花费了很长时间才想到使用量子力学系统来进行信息处理。要了解其中的缘由，我们必须回顾历史，逐一考察为量子计算和量子信息提供基本概念的所有领域——量子力学、计算机科学、信息论和密码体系。在此过程中，为了对已自成一体的量子计算和量子信息的各方面有所了解，我们需要先后采用物理学家、计算机科学家、信息论学家和密码学家的视角。

由Michael A. Nielsen和Isaac L. Chuang合著的《Quantum Computation and Quantum Information》毫无疑问是量子计算和量子信息领域最优秀的教材之一，全书近700页，覆盖了量子计算和量子信息的基础知识。

中国科学院计算所孙晓明研究员领衔，邀请了数学所尚云教授、中山大学李绿周教授、北理工尹璋琦教授、清华大学魏朝晖助理教授和中科院计算所田国敬副研究员等五位活跃在量子计算一线的研究人员，从2018年9月开始翻译此书，直到2020年夏天完成翻译初稿，之后又花了一年的时间打磨校对，可谓呕心沥血，为关心量子计算的读者提供了一本高质量的译作《量子计算与量子信息：10周年版》。

本文经授权摘选自《量子计算与量子信息：10周年版》，标题为编辑所加。文末有惊喜！

20世纪初叶，科学经历了一场出人意料的革命。物理学遇到了一系列危机。问题在于当时的物理学理论（现称为经典物理学）做出了一些荒谬的预言，例如存在包含无限能量的“紫外灾难”，或电子必然会螺旋进入原子核内部。起初，通过在经典物理学中加入特殊假设，这些问题得以解决，但随着人们对原子和辐射有了更好的理解，这些解释越来越使人困惑。在经历了四分之一世纪的混乱后，危机于20世纪20年代早期到达顶峰，最终导致了量子力学这一现代理论的创立。自此以后，量子力学一直是科学不可或缺的一部分，并已有无数成功应用的例子，包括原子结构、恒星核聚变、超导体、DNA结构，以及自然界基本粒子等几乎所有方面。

紫外灾难

什么是量子力学？量子力学是一个数学框架或物理理论构建的规则集。例如，量子电动力学就是一套以极其精确的方式刻画原子与光的相互作用的物理理论。量子电动力学是在量子力学的框架下建立起来的，但还包含量子力学未规定的一些特殊规则。量子力学与像量子电动力学那样的特定物理理论的关系，更像是计算机操作系统与特定应用软件的关系——操作系统设置某些基本参数和操作模式，而应用软件则完成特定任务。

量子力学的规则很简单，但即使专家有时也会感到它违背直觉，量子计算和量子信息的先驱一直期盼能对量子力学有更好的理解。最著名的量子力学批判者阿尔伯特·爱因斯坦（Albert Einstein），直到去世都不能接受他帮助发展起来的这一理论。几代物理学家一直在努力使量子力学的预言更加令人满意。量子计算和量子信息的目标之一是开发工具以增进对量子力学的直观把握，并使其预言对人们更通俗易懂。

爱因斯坦：上帝不会掷骰子

例如，在20世纪80年代早期，人们开始关注是否有可能使用量子效应进行超光速的信号传递——根据爱因斯坦的相对论，这是不可能的。这个问题的解决最终取决于是否有可能克隆未知量子态，即复制量子态。如果克隆是可能的，那么就有可能借助量子效应进行超光速的信号传递。尽管克隆对于经典信息很容易实现（想想看本书中的信息来自哪里！），但在量子力学的一般意义下是不可能的。这条在20世纪80年代早期就发现的不可克隆定理是量子计算和量子信息的早期成果之一。此后不可克隆定理有了许多改进，我们现在已经有了可以了解量子克隆设备（必然是不完美的）能力的工具。这些工具反过来已被用于理解量子力学的其他方面。

有助于量子计算和量子信息发展的相关历史链可追溯到20世纪70年代对单量子系统的完全操控的兴趣。在那之前，量子力学的应用通常涉及对包含大量量子力学系统的批量样品的总体控制，而单个量子力学系统则无法单独访问。例如，超导现象具有极好的量子力学解释，但由于超导体涉及导电金属的巨大样本（与原子尺度相比），所以只能探测到其量子力学性质的几个方面，而无法触及构成超导体的单个量子系统。虽然粒子加速器可以让我们有限度地访问单个量子系统，但是几乎无法对其实施控制。

自20世纪70年代以来，有许多用于控制单量子系统的技术诞生。例如，用于捕获单个原子的“原子陷阱”，可使原子与其环境隔离，并对原子行为的很多方面进行极其精密的探测。扫描隧道显微镜可用于移动单个原子，按要求设计原子阵列。还有可以转移单个电子的电子器件。

为何要试图完全控制单量子系统？抛开许多技术的原因，从纯粹科学的角度看，主要原因是研究人员预感到，科学上最深刻的见解往往出现在开发探索新的自然领域方法之时。例如，20世纪30年代到40年代的射电天文学发明导致了一系列惊人的发现，包括银河系的中心、脉冲星和类星体等。低温物理学的惊人成就也是在人们寻找降低不同系统温度的方法时取得的。同样地，通过完全控制单量子系统，我们正在探索自然的未知领域，希望发现新的和意外的现象。我们在这些方向上刚迈出第一步，就已经在这个领域中有了几项有趣的发现。一旦能够完全操控单量子系统，我们又会发现什么呢？

量子计算和量子信息研究天然适合这一计划。它为人们设计更好地操纵单量子系统的方法提供了一系列有价值的挑战，促进了新的实验技术的发展，并指出了实验研究中最有趣的方向。反过来，操控单量子系统对于把量子力学的威力应用于量子计算和量子信息研究是必不可少的。尽管人们有着浓厚的兴趣，但建立量子信息处理系统的努力迄今只取得了初步的成功。能够在几个量子比特（或量子位）上进行几十次操作的小型量子计算机代表了目前量子计算的最高水平。用于长距离保密通信的量子密码学（quantum cryptography）的实验原型已经出现，并且可用于某些实际应用。然而，如何制造可解决实际问题的大规模量子信息处理设备，仍是物理学家和工程师未来面临的巨大挑战。

20世纪另一项伟大的智慧成就——计算机科学。计算机科学的起源可以追溯到很久以前。例如，楔形文字片表明，在汉谟拉比（Hammurabi，约公元前1750年）时代，巴比伦人（Babylonian）已有相当复杂的算法思想，有些思想甚至可以追溯到更早的年代。

伟大的数学家阿兰·图灵（Alan Turing）在1936年发表的一篇令人瞩目的论文宣告了现代计算机科学的诞生。图灵以抽象的方式详细描述了我们现在所说的可编程计算机，即以他的名字命名的图灵机的计算模型。图灵证明了存在一台通用图灵机，可用于模拟任何其他图灵机。此外，他宣称通用图灵机完全刻画了算法手段所能完成的所有任务。即任何可以在硬件（如现代个人计算机）上执行的算法，在通用图灵机上都有等效算法来完成。这个论断被称为丘奇–图灵论题（Church-Turing thesis），以图灵和另一位计算机科学先驱阿隆佐·丘奇（Alonzo Church）的名字命名，它断言了在某一物理设备上可以实现的算法与数学上严格定义的通用图灵机概念的等价关系。人们普遍认为，该论题为计算机科学丰富的理论发展奠定了基础。

阿兰·图灵

在图灵的论文发表后不久，第一台电子计算机诞生。约翰·冯·诺伊曼（John von Neumann）设计了一个简单的理论模型，用实际元件实现了通用图灵机的全部功能。到了1947年，在JohnBardeen、Walter Brattain和Will Shockley发明晶体管后，硬件才开始蓬勃发展。从那时起，计算机硬件的能力以惊人的速度增长，以至于1965年戈登·摩尔（Gordon Moore）将其概括为摩尔定律，即计算机的能力将以恒定的速率增长，大约每两年增长一倍。

令人惊讶的是，自20世纪60年代开始，摩尔定律在几十年里都近似成立。尽管如此，但大多数研究人员都预计这将在21世纪的前20年内终结。传统的计算机制造方法在解决线宽尺度所带来的根本性困难时开始显得力不从心。随着电子器件越来越小，其功能会受到量子效应的干扰。

解决摩尔定律最终失效问题的一个可能方案是采用不同的计算模式。量子计算理论就是这样的一种范例，它基于量子力学而不是经典物理学的思想来执行计算。事实证明，虽然普通计算机可用于模拟量子计算机，但似乎不能以一种有效的方式去模拟。因此，量子计算机相比传统计算机在速度上有本质的超越。这种速度优势非常显著，以至于许多研究人员认为，经典计算机和量子计算机的能力之间存在着无法跨越的鸿沟。

量子计算机的“有效”与“非有效”模拟是指什么？早在量子计算机的概念出现之前，回答这个问题所需的许多关键概念实际上就已被定义。特别是计算复杂性领域在数学上精确地定义了“有效”和“非有效”算法。粗略地说，有效算法解决问题所用的时间是关于问题规模的多项式量级。相反，非有效算法需要超多项式（通常是指数量级）的时间。

在20世纪60年代末到70年代初，人们注意到通过用图灵机来模拟其他计算模型，在其他模型上能够有效解决的问题也能够在图灵机上高效解决，这意味着图灵机这一计算模型并不逊色于任何其他计算模型。这一观点可概括为加强版丘奇–图灵论题：使用图灵机可以有效地模拟任何算法过程。

强丘奇–图灵论题的加强之处在于“有效”一词。如果这一论题正确，就意味着无论用何种机器执行算法，都可以使用标准图灵机有效模拟。这一强化很重要，因为它意味着要分析给定的计算任务是否可以有效完成，可以限定在图灵机的计算模型上进行。

强丘奇–图灵论题面临的一类挑战来自模拟计算领域。在图灵所处的时代，许多不同的研究团队已经注意到某些类型的模拟计算机可以有效地解决在图灵机上没有有效解决方案的问题。表面上看，这些模拟计算机似乎违反了强丘奇–图灵论题。不幸的是，对于模拟计算机，在对噪声做出符合实际的假设后，其计算能力在所有已知的例子里都会消失，它们也不能有效地解决图灵机无法有效解决的问题。这个教训——在评估计算模型的效率时必须考虑现实噪声的影响——是量子计算和量子信息初期面临的最大挑战之一，这一挑战随着量子纠错码和容错量子计算理论的发展得到了有效的解决。因为与模拟计算不同，量子计算原则上可以容忍有限的噪声并保持其计算优势。

对强丘奇–图灵论题的第一个重大挑战出现在20世纪70年代中期，当时Robert Solovay和Volker Strassen证明了可以使用随机算法测试一个整数是否是素数。也就是说，随机性是SolovayStrassen测试算法的实质部分。该算法并不能确定给定的整数是素数还是合数。相反，它可以给出一个数是素数或合数的概率。通过重复Solovay-Strassen测试，几乎可以确定一个数是素数还是合数。Solovay-Strassen测试算法的重要意义在于该算法提出时，素数判定问题并没有有效的确定型算法。于是，似乎带有随机数发生器的计算机能够有效执行某个计算任务，而这一任务在经典的确定型图灵机上却不能有效解决。这一发现激励着人们去寻找其他随机算法并获得了丰厚的回报，它也因此成为了一个活跃的研究领域。

随机算法形成了对强丘奇–图灵论题的挑战，这暗示着存在一些可以有效求解的问题，但它们不能被确定型图灵机有效地求解。这一挑战可以通过对强丘奇–图灵论题稍做修改来解决：任何算法都可以用概率图灵机有效模拟。对强丘奇–图灵论题的这种即兴修改令人深感不安。将来难道一定不会有另外一种计算模型能有效解决图灵计算模型中无法有效解决的问题？有没有什么途径可以找到一个能有效地模拟其他任何计算模型的计算模型？

受这个问题的启发，David Deutsch在1985年提出，是否可以用物理学定律推导出更强的丘奇–图灵论题。Deutsch没有用特定假设的方法，而是通过物理学理论为丘奇–图灵论题建立和当今物理学理论前沿相当的基础。特别地，Deutsch试图定义一种能够有效模拟任意物理系统的计算设备。由于量子力学是物理学的最终规律，Deutsch自然而然地考虑了基于量子力学原理的计算设备。这些设备，仿照49年前图灵定义的机器，最终引导出了本书中现代量子计算机的概念。

Deutsch量子计算机模型确实对强丘奇–图灵论题提出了挑战。Deutsch曾询问量子计算机是否可以有效解决在经典计算机上不能有效解决的计算问题，甚至是概率图灵机不能有效解决的计算问题。然后他举了一个简单的例子，表明量子计算机的计算能力确实超过了传统计算机。

随后的十年内许多人努力改进Deutsch令人瞩目的初步结果，直到1994年Peter Shor展示了两个非常重要的问题——寻找整数的素因子问题和所谓的离散对数问题——可以在量子计算机上有效解决，而达到顶点。这方面的研究之所以受到广泛关注，是因为人们普遍认为这两个问题在经典计算机上没有有效的解决方案。Shor的成果是量子计算机比图灵机及概率图灵机更强大的有力证据。量子计算机功能强大的进一步证据出现在1995年，Lov Grover证明了另一重要问题——在非结构化搜索空间进行搜索的问题——也可以在量子计算机上得到加速。虽然Grover的算法并没有像Shor算法那样有惊人的加速，但搜索方法的广泛应用引起了人们对Grover算法的极大兴趣。

与传统计算机相比，量子计算机还能更快地解决其他哪些问题？简短的回答是我们不知道。找出好的量子算法似乎很难。悲观主义者可能会认为除了已发现的应用，量子计算机并没有其他好处！设计量子计算机算法的困难之处在于，设计者面临经典计算机算法所未遇到的两方面难题。首先，人类的直觉植根于经典世界。如果借助于直觉来构建算法，则只能想到经典思想。为设计好的量子算法，我们必须至少部分地“关闭”经典直觉，利用量子效应去达到期望的算法目的。其次，要想真正有意义，光设计出一个纯粹的量子算法是不够的。这些算法必须优于任何现有的经典算法！因此，人们或许可以找到一种利用纯量子力学的算法，但由于已经存在性能具有可比性的经典算法而未引起广泛关注。这两个问题的结合使得新量子算法的设计成为未来的挑战。

更一般地说，是否可以归纳出量子计算机与经典计算机能力的差别。如果量子计算机真的比传统计算机更强大，那让它更强的原因是什么？什么类型的问题可以在量子计算机上有效地解决，与经典计算机上可有效解决的问题相比如何？量子计算和量子信息中最激动人心的事情之一，就是对这些问题的答案知之甚少！更好地理解这些问题是未来的一个巨大挑战。

未来会如何？量子计算和量子信息会给科学、技术和人类带来什么？量子计算和量子信息能对产生它的计算机科学、信息论和物理学诸领域带来什么好处？量子计算和量子信息有哪些关键问题尚未解决？

量子计算和量子信息教会我们以物理的方式对计算进行思考，我们发现这种做法能为信息处理和通信带来许多新的令人鼓舞的动力。计算机科学家和信息论专家有了一个值得探索的内容丰富的新模型。实际上广义来说，我们学到的任何物理理论，不仅仅是量子力学，都可以作为信息处理和通信的基础。这种探索的结果，也许有朝一日会导致发明远超出当今计算和通信系统能力的信息处理装置，并对整个社会相应带来正面和负面的影响。

量子计算和量子信息无疑给物理学家带来了很多挑战，但从长远来看它对物理学做出何种贡献却有些微妙。我们相信，正如我们学会用物理的方式思考计算一样，我们也能学会用计算的方式思考物理学。虽然传统物理学主要集中于弄清基本物体和简单系统，但自然的许多有趣方面只会在事物变得更大和更复杂时出现。化学和工程在某种程度上处理了这种复杂性，但大多数情况下都是以就事论事的方式。量子计算和量子信息传达的一个信息是，新的工具可以用来跨越微小和相对复杂的事物之间的鸿沟：计算与算法为构建和理解此类系统提供了系统化的手段。应用这些领域的思想已经开始对物理学带来新的见解。我们希望多年后它将发展成为一个理解物理学所有分支的富有成果的方向。

噪声是信息处理系统的重大障碍。当条件允许的时候，人们总是尽量彻底地消除噪声；在实在做不到的情况下，人们则尝试保护有用信息，使其不受噪声影响。例如，现代电子计算机的部件极其可靠，错误率已经低到每完成1017次操作仅出现不到一次错误。因此，在大部分实际计算任务中，我们可以将计算机当作彻底无噪声的。然而另一方面，许多广泛应用的信息系统却遭受着噪声的严重影响。例如，调制解调器和CD播放器都采用纠错码来抵御噪声的影响。实际上，现实生活中对抗噪声的技术经常有非常复杂的细节，但它们的基本原理都非常好理解：如果我们希望保护一条信息免受噪声的影响，我们一般都会使用一些冗余信息来编码这条信息。如此一来，即使编码后的信息中有一部分被噪声破坏，编码信息依然拥有足够的冗余度来使得我们能够很好地解码和恢复原本的信息。而冗余信息的多少，将取决于信道中噪声的严重程度。

为了保护量子信息免受噪声影响，我们需要基于类似的原理发展量子纠错码理论。由于量子信息和经典信息的众多区别，量子纠错码的引入需要面临很多困难：

1. 不可克隆。量子拥有不可克隆原理——无法通过将量子信息重复多次的方式来实现量子重复性编码；

2. 错误是连续的。可能发生在一个量子比特上的错误是连续的，因此，确定具体哪个错误确实发生并纠正需要无线的精确度去分辨；

3. 测量破坏量子信息。在经典纠错中，我们先观察信道的输出，然后决定采用何种解码方案；但是在量子纠错方案中，观察量子信息将破坏它，因而无法恢复原有信息。

那我们能否建立一套量子纠错码的一般性理论？

Shor编码本质上是三量子比特相位翻转编码和比特翻转编码的结合，因而可以有效对抗单量子比特上的任何错误。量子纠错码理论的基本想法就是自然推广Shor编码的思路：通过一个酉变换，量子态被编码成量子纠错码——严格来说是某个更大的希尔伯特空间的子空间C。在噪声作用到编码后的的量子态上之后，我们通过征状测量去诊断所发生的是何种错误；一旦错误被确定后，我们将进行恢复操作，将量子系统恢复到原本的编码状态。简单来说，量子纠错可以被描述为一个两阶段过程：量子测量驱动的错误探测，和条件酉操作完成的信息恢复。

基于上述量子理论框架，目前科学家已经发展出经典线性编码、Calderbank-Shor-Steane（CSS）编码和稳定子编码。

相对于一般纠错码，线性码的一个巨大优势是其紧凑的描述：将k个比特编码到n个比特上的一般性编码，需要有2^k个码字，每个的描述长度为n，因此总共需要n2^k个比特来描述整个纠错码；但是同样规格的线性码只需要kn个比特来描述，因而节省了指数数量的存储空间。经典线性码的对偶构造方法，在量子纠缠码中也会自然出现，并且是CSS编码的重要纠错码的关键所在：假设C₁和C₂分别是[n,K₁]和[n,k₂]的经典线性编码，C₂C₁，而且C₁和C都能纠正至多t个错误，那么CSS（C₁，C₂）是一个能纠正至多t个量子比特上任意错误的[n,k₁-k₂]量子纠错码。

稳定子形式的基本思想是，对于许多量子态，用稳定它们的算子来描述经常比直接描述状态本身更加方便。因而，稳定子形式是量子纠错码的理想描述方法；稳定子编码的一大特征就是它们的结构使得编码、解码和纠错程序的系统性构造成为可能。同时，可以用稳定子描述酉操作和测量的事实，也可以总结为著名的Gottesman-Knill定理：假设量子计算中只涉及以下操作，分别是计算基下的状态制备、阿达玛门、相位门、受控非门、泡利门、泡利群中可观测对应的测量，和基于量子测量结果的经典控制，则这种量子计算可以被经典计算机有效模拟。回顾一些有趣的量子信息处理方案，比如量子隐形传态、超密编码，它们都能被阿达玛门、受控非门和计算基下测量实现，因此都可以被经典计算机模拟。

量子纠错最强大的应用，不仅仅是用来保护存储或传递的量子信息，更是用来保护计算中动态变化的量子信息。根据量子计算阈值定理——大规模量子计算的物理实现没有原则性障碍，借助容错量子计算，即使逻辑门是有瑕疵的，只要每个逻辑门的错误概率低于某个阈值，原则上任何精确的量子计算都可以实现。

容错量子计算理论的基本想法是，在合理编码后的量子态上直接进行量子计算，以至于完全不需要做解码操作。假设我们有一个简单量子电路，但不幸的是噪声影响着这个电路的每一个元件，包括量子态的制备、量子逻辑门、对输出的测量，甚至量子信息在电路中的简单传递。为了对抗噪声的影响，我们可以用类似七量子比特Steane码的纠错码编码方式，将原电路中的每一个量子比特用一个量子比特区块来替代，同时将原电路中的每一个逻辑门用作用在逻辑量子比特上的编码逻辑门替代。通过周期性地在编码后的量子态上进行纠错操作，我们能够阻止错误在量子态中的积累。当然，即使在每个编码逻辑门后都实施，仅仅依靠周期性纠错还不足以阻止噪声的出现。原因是两方面的：首先最重要的是编码逻辑门可能会导致错误的传输。例如，编码受控非门可能会导致一个编码控制量子比特中的错误传播到编码目标量子比特上，因此前者中的错误可能会变成后者中的错误。因此，为了让纠错能有效地消除噪声，在编码逻辑门执行过程中任何位置的错误只能传播到编码数据中每个区块的少数位置，这种实现编码逻辑门的程序，被称为容错程序。量子纠错第二个需要解决的问题是，纠错程序自己也会引入错误，因此我们必须小心地设计纠错程序，这可以通过类似编码逻辑门中组织错误传播的技术来实现。

因此，一个过程是容错的可以定义为，如果这个过程中的一个组成部分发生错误，那么这个错误在过程最后输出的每一个量子比特区块中，至多产生一个错误。容错理论基于编码后数据的计算、量子电路的基本噪声模型等理论想法，最终结合编码级联技术，得出了量子纠错码理论最突出的成就——量子计算的阈值定理：假设单个量子门的噪声低于某个常数阈值，并且满足某些物理上合理的假设，则可以可靠地实现任意长的量子计算，并且为了确保可靠性，多出的代价跟电路的规模比很小。

本书介绍了量子计算和量子信息领域的主要思想和技术。该领域的快速发展及其跨学科的性质使得新来者很难全面地了解其中重要的技术和研究成果。

本书共分为3部分：  

● 第1部分概述了量子计算和量子信息领域的主要思想和研究成果，并介绍了计算机科学、数学和物理学领域的相关背景材料，这些材料是深入理解量子计算和量子信息所必需的；

● 第2部分详细描述了量子计算；

● 第3部分是关于量子信息的，内容涉及什么是量子信息，如何使用量子态表示和交流信息，以及如何描述和处理量子信息和经典信息的破坏。

---

参与光子盒话题讨论，将有机会获得这本被誉为量子计算“圣经”的《量子计算与量子信息：10周年版》（中文）。本次讨论的话题是：

你认为量子计算机可以用来做什么？

欢迎在评论区留言，我们将为获得点赞数前三（3月28日上午10点截止）的朋友每人赠送一本《量子计算与量子信息：10周年版》。

领取书籍需在3月29日下午6点之前主动添加盒叔微信（Hordcore），并提供收货地址。

没有获得赠书机会的朋友，可以通过扫描下图中的二维码或点击文末左下角的“阅读原文”购买。

—End—

相关阅读：

光子盒将为中国境内的研究机构和企业提供一个免费的垂直招聘信息发布渠道，欢迎有需求的机构或企业直接联系光子盒。（微信：Hordcore）

你可能会错过：